/*
 * Transmissão de Dados - Trabalho 4
 *
 * Alex Oliveira   - 06/30403
 * Danilo Trindade - 06/82039
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "grafo.h"

#define MINDIMENSAO 10
#define MAXDIMENSAO 100000
#define MINRAIO 2
#define MAXRAIO 100
#define MINQUANTIDADE 3
#define MAXQUANTIDADE 100000

static void recebe_parametros(int argc, char **argv);
static void troca_tabelas(grafo_t grafo);
static void mostra_rota(grafo_t grafo, int orig, int dest);
static void escreve_resultado(grafo_t grafo);
static bool houve_atualizacao(grafo_t grafo, bool* atualizou);

static int altura, largura, raio, quantidade;
int quant_arestas = 0, num_trocas = 0, max_dist = 0;


int main(int argc, char **argv) {

	/* Valida os parâmetros do programa e inicia as variáveis estáticas globais. */
	recebe_parametros(argc, argv);

	/* Cria a matriz e o grafo. */
	matriz_t matriz = new_matriz(altura, largura, quantidade, raio);
	grafo_t grafo = new_grafo(matriz, raio);
	del_matriz(matriz);

	/* Faz todos os comutadores trocarema as tabelas até estabilizar. */
	troca_tabelas(grafo);

	/* Mostra a rota de cada vértice para todos os outros. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		for (int j = 0; j < grafo.quant_vertices; j++){
			if (i != j){
				mostra_rota(grafo,i,j);
			}
		}
	}

	/* Escreve os resultados estatísticos acumulados durante a simulação. */
	escreve_resultado(grafo);

	del_grafo(grafo);
	return 0;
}


/*
 * Inicializa as variáveis estáticas desse arquivo com os parâmetros recebidos
 * pelo programa.
 */
void recebe_parametros(int argc, char **argv) {
	if (argc < 5) {
		puts("Quantidade de parâmetros incorreta. Chame o programa da seguinte forma:\n"
				"\tdistancevector <altura> <largura> <raio> <quantidade>\n"
				"onde <altura> e <largura> são as dimensões da matriz, <raio> é "
				"a distância aproximada máxima entre um nó e outro e "
				"<quantidade> é o número de vértices do grafo.");
		exit(EXIT_FAILURE);
	}
	altura = atoi(argv[1]);
	largura = atoi(argv[2]);
	if (altura < MINDIMENSAO || altura > MAXDIMENSAO || largura < MINDIMENSAO || largura > MAXDIMENSAO) {
		printf("A altura e a largura devem estar entre %d e %d\n", MINDIMENSAO, MAXDIMENSAO);
		exit(EXIT_FAILURE);
	}
	raio = atoi(argv[3]);
	if (raio < MINRAIO || raio > MAXRAIO) {
		printf("O raio deve estar entre %d e %d\n", MINRAIO, MAXRAIO);
		exit(EXIT_FAILURE);
	}
	quantidade = atoi(argv[4]);
	if (quantidade < MINQUANTIDADE || quantidade > MAXQUANTIDADE) {
		printf("A quantidade deve estar entre %d e %d\n", MINQUANTIDADE, MAXQUANTIDADE);
		exit(EXIT_FAILURE);
	}
	if (largura < 2*raio || altura < 2*raio) {
		puts("A largura e a altura devem ser bem maiores que o raio.");
		exit(EXIT_FAILURE);
	}
}


/*
 * Coloca todos os comutadores para trocar suas tabelas até estabilizar.
 */
void troca_tabelas(grafo_t grafo) {

	int **tabela_custo;
	bool *atualizou, *ira_atualizar;

	atualizou = calloc(grafo.quant_vertices, sizeof(bool));
	ira_atualizar = calloc(grafo.quant_vertices, sizeof(bool));
	tabela_custo = malloc(grafo.quant_vertices * sizeof(int *));

	/* Prepara tabela de custos antigos para simular paralelismo. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		tabela_custo[i] = malloc(grafo.quant_vertices * sizeof(int));
		for (int j = 0; j < grafo.quant_vertices; j++){
			tabela_custo[i][j] = grafo.custo[i][j];
		}
		atualizou[i] = true;
		ira_atualizar[i] = false;
	}

	while(houve_atualizacao(grafo, atualizou)){ /* Se houve alguma atualizacao */

		for (int i = 0; i < grafo.quant_vertices; i++){ /* Percorre todos so nos */
			if (atualizou[i]) { /* Se o no atualizou */
				for (int j = 0; j < grafo.quant_vizinhos[i]; j++){ /* Percorre todos os vizinhos do no atualizado */
					for (int k = 0; k < grafo.quant_vertices; k++){ /* Pra todos os caminhos que existem no no atualizado */
						/* 
						 * Se o custo que este no atualizado tiver pro no 'k', ao ser somado ao custo q ele tem pra ir ate o
						 * no que eh o vizinho 'j' dele for menor q o custo desse vizinho ir ao no 'k', entao atualiza o
						 * custo e o caminho do vizinho em questao, e marca ele como ira ser atualizado pra enviar sua tabela
						 * na proxima iteracao.
						 *  
						 * usar o seguinte printf para verificar o if:
						 * printf("custo de %d pra %d: %d + custo de %d pra %d: %d < custo de %d pra %d: %d?\n",
						 * i, k, tabela_custo[i][k], i, grafo.vizinho[i][j], tabela_custo[i][grafo.vizinho[i][j]],
						 * grafo.vizinho[i][j], k, grafo.custo[grafo.vizinho[i][j]][k]);
						 * getchar();
						 */
						if ((tabela_custo[i][k] + tabela_custo[i][grafo.vizinho[i][j]]) < grafo.custo[grafo.vizinho[i][j]][k]){
							
							grafo.custo[grafo.vizinho[i][j]][k] = (tabela_custo[i][k] + tabela_custo[i][grafo.vizinho[i][j]]);
							grafo.caminho[grafo.vizinho[i][j]][k] = i;
							ira_atualizar[grafo.vizinho[i][j]] = true;
							
							for (int l = 0; l < grafo.quant_vertices; l++){
								if ((k != l) && (grafo.caminho[grafo.vizinho[i][j]][l] == k)){
									grafo.custo[grafo.vizinho[i][j]][l] = (grafo.custo[i][l] + grafo.custo[i][grafo.vizinho[i][j]]);
								}
							}
							
						}
					}
					num_trocas++;
				}
			}
		}

		/* Monta o vetor de quais atualizaram pra proxima iteracao. */
		for (int i = 0; i < grafo.quant_vertices; i++){
			atualizou[i] = ira_atualizar[i];
			ira_atualizar[i] = false;
		}

		/* Atualiza tabela de custos com o valor antigo. */
		for (int i = 0; i < grafo.quant_vertices; i++){
			for (int j = 0; j < grafo.quant_vertices; j++){
				
				tabela_custo[i][j] = grafo.custo[i][j];
				
				
			}
		}

	}

	/* Atualiza caminhos otimizados das tabelas. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		for (int j = 0; j < grafo.quant_vertices; j++){
			if (grafo.caminho[i][j] != j){
				for (int k = 0; k < grafo.quant_vertices; k++){
					if (grafo.caminho[i][k] == j){
						grafo.caminho[i][k] = grafo.caminho[i][j];
					}
				}
			}
		}
	}
	
	/* Libera memória utilizada. */
	for (int i = 0; i < grafo.quant_vertices; i++){
		free(tabela_custo[i]);
	}
	free(tabela_custo);
	free(atualizou);

	return;
}


/*
 * Lê do usuário um nó origem e um destino e escreve a menor rota e o custo dela.
 */
void mostra_rota(grafo_t grafo, int orig, int dest){

	int rota[grafo.quant_vertices], i = 0;

	rota[i] = orig;

	/* Monta a rota que será seguida pra ir de orig a dest. */
	while (rota[i] != dest){
		i++;
		rota[i] = grafo.caminho[rota[i-1]][dest];
	}

	/* Imprime o melhor caminho, seu custo e o número de pulos que faz. */
	printf("Menor caminho do no %d para o no %d:\n Pulos: %d\n Rota: %d -> ", orig, dest, i, orig);
	for (int j = 1; j<i; j++){
		printf("%d -> ", rota[j]);
	}
	printf("%d\n Custo: %d\n", dest, grafo.custo[orig][dest]);

	return;
}


/*
 * Escreve as estatísticas acumuladas durante toda a simulação.
 */
void escreve_resultado(grafo_t g) {

	/* Calcula a quantidade de arestas. */
	for (int i = 0; i < quantidade; ++i) {
		quant_arestas += g.quant_vizinhos[i];
	}
	quant_arestas /= 2;  /* cada aresta foi contada duas vezes */

	/* Escreve na tela. */
	printf("Quantidade de vértices: %d\n"
			"Quantidade de arestas: %d\n"
			"Quantidade de trocas de tabela: %d\n",
			quantidade, quant_arestas, num_trocas);
}


/*
 * Verifica se alguma tabela foi atualizada. Retorna TRUE se for
 * e FALSE caso contrário.
 */
bool houve_atualizacao(grafo_t grafo, bool* atualizou){

	bool troca = false;

	for (int i = 0; i < grafo.quant_vertices; i++){
		if (atualizou[i]){
			troca = true;
		}
	}

	return(troca);
}
